/**
 * Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.
 */
package com.xinpan.exercise;

public class MinPathSum {
    public int minPathSum(int[][] grid) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int h = grid.length;
        if(h == 0)
            return 0;
        int w = grid[0].length;
        if(w == 0)
            return 0;
        
        int[][] cost = new int[h][w];
        
        cost[0][0] = grid[0][0];
            
        for(int i = 1; i < h; i++)
        {
            cost[i][0] = cost[i-1][0] + grid[i][0];
        }
        for(int i = 1; i < w; i++)
        {
            cost[0][i] = cost[0][i-1] + grid[0][i];
        }
        
        
        for(int i = 1; i < h; i++)
        {
            for(int j = 1; j < w; j++)
            {
                int min = Math.min(cost[i-1][j], cost[i][j-1]);
                cost[i][j] = min + grid[i][j];
            }
        }

        return cost[h-1][w-1];
    }
    
    public static void main(String[] args)
    {
    	MinPathSum mps = new MinPathSum();
    	int[][] grid = {{1,2,5},{3,2,1}};
    	grid[0][0] = 0;
    	mps.minPathSum(grid);
    }
}
